package com.mango.algorithm.tree.binary;

import com.mango.data.structure.binarytree.linknode.TreeNode;

/**
 * 平衡二叉树，以树形DP套路解决问题
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
 * @Author: mango
 * @Date: 2022/4/11 9:33 下午
 */
public class BalanceTree {

    public boolean isBalanced(TreeNode node){
        return getInfo(node).isBalance;
    }
    // 递归手机信息
    public Info getInfo(TreeNode node){
        if(node == null){
            return new Info(0,true);
        }
        // 搜集左树信息
        Info leftInfo = getInfo(node.left);
        // 搜集右树信息
        Info rightInfo = getInfo(node.right);

        // 高度等于左树和右树高的那个+1
        int height = Math.max(leftInfo.height,rightInfo.height) + 1;
        // 是否平衡等于左右都平衡且高度相差小于2
        boolean isBalance = leftInfo.isBalance && rightInfo.isBalance
                && Math.abs(leftInfo.height-rightInfo.height) < 2;

        return new Info(height,isBalance);
    }
}
// 信息体
class Info{
    public int height;
    public boolean isBalance;
    public Info(int height,boolean isBalance){
        this.height = height;
        this.isBalance = isBalance;
    }
}
